/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-11-08
 * Time: 15:20
 */
public class MySingleLinkedList implements ISingleLinkedList {

    ListNode head;

    int usedSize;

    public static class ListNode{
        int val;
        ListNode next;
        ListNode() {

        }
        ListNode(int val) {
            this.val = val;
        }
    }

//    头插法
    @Override
    public void addFirst(int data) {
        ListNode newN = new ListNode(data);
        if (this.head == null){
            this.head = newN;
            return;
        }
        newN.next = head;
        this.head = newN;
        this.usedSize++;
    }

//    尾插法
    @Override
    public void addLast(int data){
        ListNode newH = new ListNode(data);
        if (this.head == null){
            this.addFirst(data);
            return;
        }
        ListNode cur = this.head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = newH;
        this.usedSize++;
    }

//    在指定位置插入
    @Override
    public boolean addIndex(int index, int data) {
        if (!this.checkIndex(index)){
            return false;
        }

        if (this.head == null){
            return false;
        }
        ListNode cur = this.head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        ListNode newN = new ListNode(data);
        newN.next = cur.next;
        cur.next = newN;
        return true;
    }

//    判断链表中是否有某个数值
    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

//    删除第一个值为key的节点
    @Override
    public void remove(int key) {
        if (this.head == null){
            return;
        }
        if (!this.contains(key)){
            return;
        }
        if (this.head.val == key){
            this.head = this.head.next;
            this.usedSize--;
            return;
        }
        ListNode cur = this.head;
        ListNode curN = cur.next;
        while (curN.val != key){
            cur = curN;
            curN = curN.next;
        }
        if (cur == null){
            return;
        }
        cur.next = curN.next;
        this.usedSize--;
    }

//    删除所有值为key的节点
    @Override
    public void removeAllKey(int key) {
        if (this.head == null){
            return;
        }
        if (!this.contains(key)){
            return;
        }
        while (this.head.val == key){
            this.head = this.head.next;
        }
        ListNode cur = this.head;
        ListNode curN = cur.next;
        while (curN != null){
            if (curN.val == key){
                cur.next = curN.next;
                this.usedSize--;
            }
            cur = curN;
            curN = curN.next;
        }
    }

//    获取链表长度
    @Override
    public int size() {
        return this.usedSize;
    }

//    打印链表
    @Override
    public void display(){
        ListNode cur = this.head;
        System.out.print("[ ");
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println("]");
    }

//    打印指定位置开始的ListNode链表
    public void display(ListNode head){
        ListNode cur = head;
        System.out.print("[ ");
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println("]");
    }

//    获取链表的中间节点
    public ListNode middleNode(ListNode numHead) {
        if (numHead == null){
            return null;
        }
        ListNode fast = numHead;
        ListNode slow = numHead;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

//    移除所有值为indexValue的节点
    public ListNode removeElements(ListNode head, int indexValue) {
        if (head == null){
            return null;
        }
        while (head.val == indexValue){
            head = head.next;
            if (head == null){
                return null;
            }
        }
        ListNode cur = head;
        while (cur.next != null){
            ListNode curN = cur.next;
            if (curN.val == indexValue){
                cur.next = curN.next;
            }else {
                cur = cur.next;
            }
        }
        return head;
    }

//    反转head之后的链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode cur = head;
        ListNode curN = cur.next;
        while (curN != null){
            ListNode temp = curN.next;
            curN.next = cur;
            cur = curN;
            curN = temp;
        }
        head.next = null;
        return cur;
    }

//    链表置空
    public void clear(){
        ListNode cur = this.head;
        while (cur != null){
            ListNode curN =cur.next;
            cur.next = null;
            cur = curN;
        }
        this.usedSize = 0;
        this.head = null;
    }

//    检查index的合法性
//    true为合法，false为不合法
    public boolean checkIndex(int index){
        if (index < 0 | index > this.usedSize){
            return false;
        }
        return true;
    }

//    获取链表中倒数第k个节点
    public int kthToLast(ListNode head, int k) {
        if (head == null){
            return -1;
        }
        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        ListNode slow = head;
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

//    给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
    public ListNode partition(ListNode pHead, int x) {
        ListNode cur = pHead;
        ListNode aStart = (ListNode) null;
        ListNode aEnd = (ListNode) null;
        ListNode bStart = (ListNode) null;
        ListNode bEnd = (ListNode) null;
        while (cur != null){
            if (cur.val < x){
                if (aStart == null){
                    aStart = new ListNode(cur.val);
                    aEnd = aStart;
                }else {
                    aEnd.next = new ListNode(cur.val);
                    aEnd = aEnd.next;
                }
            }else {
                if (bStart == null) {
                    bStart = new ListNode(cur.val);
                    bEnd = bStart;
                } else {
                    bEnd.next = new ListNode(cur.val);
                    bEnd = bEnd.next;
                }
            }
            cur = cur.next;
        }
        if (aStart == null){
            aStart = bStart;
        }else {
            aEnd.next = bStart;
        }
        return aStart;
    }

//    判断链表是否回文
    public boolean isPalindrome(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode cur = head;
        ListNode midCur = this.middleNode(cur);
        if (midCur.next == null){
            if (cur.val != midCur.val){
                return false;
            }
        }
        ListNode last = this.reverseList(midCur);
        while (cur != last && cur.next != last){
            if (cur.val != last.val){
                return false;
            }
            cur = cur.next;
            last = last.next;
        }
        if (cur.next == last){
            if (cur.val != last.val){
                return false;
            }
        }
        return true;
    }

//    判断链表是否成环
    public ListNode hasCycle(ListNode A){
        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return slow;
            }
        }
        return null;
    }

//    获取成环的节点
    public ListNode detectCycle(ListNode head) {
        ListNode start = head;
        ListNode intersect = this.hasCycle(head);
        if (intersect == null){
            return null;
        }
        while (start != intersect){
            start = start.next;
            intersect = intersect.next;
        }
        return start;
    }

//    获取两链表相交的节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null | headB == null){
            return null;
        }
        if (headA == headB){
            return headA;
        }
        ListNode cur = headA;
        int lenA = 0;
        while (cur != null){
            cur = cur.next;
            lenA++;
        }
        cur = headB;
        int lenB = 0;
        while (cur != null){
            cur = cur.next;
            lenB++;
        }
        int AB = lenA - lenB;
        ListNode curA = headA;
        ListNode curB = headB;
        if (AB > 0){
            for (int i = 0; i < AB; i++) {
                curA = curA.next;
            }
        }else {
            for (int i = 0; i < -AB; i++) {
                curB = curB.next;
            }
        }
        while (curA != curB){
            if (curA == null | curB == null){
                return null;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }

//    合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null){
            return null;
        } else if (list2 == null) {
            return list1;
        } else if (list1 == null){
            return list2;
        }
        ListNode newH = new ListNode();
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        if (cur1.val < cur2.val){
            newH.next = cur1;
            cur1 = cur1.next;
        }else {
            newH.next = cur2;
            cur2 = cur2.next;
        }
        ListNode curp = newH.next;
        while (cur1 != null && cur2 != null){
            if (cur1.val < cur2.val){
                curp.next = cur1;
                cur1 = cur1.next;
            }else {
                curp.next = cur2;
                cur2 = cur2.next;
            }
            curp = curp.next;
        }
        if (cur1 == null){
            curp.next = cur2;
        } else if (cur2 == null){
            curp.next = cur1;
        }
        return newH.next;
    }
}
